/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Montenegro
 */

public class Lista {
    
    //Se definen los atributos de la clase Lista
    int index; // general index
    int max; // index of largest value
    // determine maximum value in array
    
    public static void swap(int data[], int i, int j){
    // pre: 0 <= i,j < data.length
    // post: data[i] and data[j] are exchanged
        int temp;
        temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
        
    public static void selectionSort(int data[], int n){
        // pre: 0 <= n <= data.length
        // post: values in data[0..n-1] are in ascending order
        
        int numUnsorted = n;
        int index; // general index
        int max; // index of largest value
        while (numUnsorted > 0){
        // determine maximum value in array
            max = 0;
            for (index = 1; index < numUnsorted; index++){
                if (data[max] < data[index]) max = index;
            }
            swap(data,max,numUnsorted-1);
            numUnsorted--;
        }
    }
    
    private static int partition(int data[], int left, int right){
    // pre: left <= right
    // post: data[left] placed in the correct (returned) location
        while (true){
            // move right "pointer" toward left
            while (left < right && data[left] < data[right]) right--;
            if (left < right) swap(data,left++,right);
            else return left;
            // move left pointer toward right
            while (left < right && data[left] < data[right]) left++;
            if (left < right) swap(data,left,right--);
            else return right;
        }
    }
    
    public static void quickSort(int data[], int n){
        // post: the values in data[0..n-1] are in ascending order
        quickSortRecursive(data,0,n-1);
        }
    private static void quickSortRecursive(int data[],int left,int right){
    // pre: left <= right
    // post: data[left..right] in ascending order
        int pivot; // the final location of the leftmost value
        if (left >= right) return;
        pivot = partition(data,left,right); /* 1 - place pivot */
        quickSortRecursive(data,left,pivot-1); /* 2 - sort small */
        quickSortRecursive(data,pivot+1,right);/* 3 - sort large */
        /* done! */
    }
}
